

/**
 * Created by L.jp
 * Description:假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
 * User: 86189
 * Date: 2022-11-24
 * Time: 10:31
 */
public class Solution {
    //动态规划,从最大利润的求法入手，最大利润就是最高价格与最底价格的差值，利用到动态规划就是当天的价格减去历史的最小值，这就是每一个状态
   /* public int maxProfit(int[] prices) {
        if(prices==null){
            return 0;
        }
        //状态定义,dp[i]表示第i天股票的最大收益
        int[] dp=new int[prices.length];
        //成本
        int baseCount=prices[0];
        for(int i=1;i<prices.length;i++){
            //当天股票的最大收益等于前i-1天的最大收益与当天的价格减去最小值，这两者的最大值
            dp[i]=Math.max( dp[i-1],prices[i]-baseCount );
            //更新最小值
            baseCount=Math.min(prices[i],baseCount);
        }
        return dp[prices.length-1];
    }*/
    
    //优化，当天的状态至于前一天的转态有关，所以只需要使用一个变量来存储前i-1天的最大利润即可
    public static int maxProfit(int[] prices) {
        if ( prices == null ) {
            return 0;
        }
        //最终结果，最大利润
        int maxProfit=0;
        //最小值
        int minPrice=Integer.MAX_VALUE;
        for(int price:prices){
            //更新最小值
            minPrice=Math.min( price,minPrice );
            //得到每一天当天的最大利润
            maxProfit=Math.max( maxProfit,price-minPrice );
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices={7,1,5,3,6,4};
        System.out.println(maxProfit(prices));
    }
}
